//题目链接：https://leetcode.cn/problems/maximum-subarray/

class Solution 
{
public:
    int maxSubArray(vector<int>& nums) 
    {
        int n=nums.size();
        //dp[i]，以i为结尾的子数组最大和 dp[i]=max(nums[i],nums[i]+dp[i])
        int dp[n];
        dp[0]=nums[0];
        for(int i=1;i<n;i++)
        {
            dp[i]=max(nums[i],nums[i]+dp[i-1]);
        }
        int max_sum=-0xffff;
        for(auto sum:dp)
        {
            if(sum>max_sum)
                max_sum=sum;
        }
        return max_sum;
    }
};